home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graph / nfa.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.7 KB  |  282 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3. #include <LEDA/set.h>
  4. #include <LEDA/stack.h>
  5. #include <LEDA/array.h>
  6.  
  7. /* We use sets, stacks, and arrays of nodes */
  8.  
  9.  
  10.  
  11. // alphabeth: `a`,'b', ... , 'z','~'
  12.  
  13. // epsilon = '~'
  14.  
  15. const char EPSILON = '~';
  16.  
  17.  
  18. //------------------------------------------------------------------------------
  19. // NFA's are directed graphs with
  20. // node labels of type "int"  (states)
  21. // edge labels of type "char" 
  22. //------------------------------------------------------------------------------
  23.  
  24.  
  25. typedef GRAPH<int,char> NFA;
  26.  
  27. int compare(node x, node y) { return x-y; }
  28.  
  29. /*------------------------------------------------------------------------------
  30.    DFA's are directed graphs with
  31.    node labels of type set<node>*  (pointers to set of nodes of an NFA)
  32.    edge labels of type "char"      
  33. ------------------------------------------------------------------------------*/
  34.  
  35. typedef set<node>* node_set_ptr;
  36.  
  37.  
  38. typedef GRAPH<node_set_ptr,char> DFA;
  39.  
  40.  
  41.  
  42. //------------------------------------------------------------------------------
  43. // We need a test for equality on sets of nodes 
  44. // This implementation is very inefficient!
  45. //------------------------------------------------------------------------------
  46.  
  47. bool EQ_NODE_SET(node_set_ptr S1, node_set_ptr S2)
  48. {
  49.   // input: two pointers S1 and S2 to sets of nodes
  50.   // ouput: true,  if node sets *S1 and *S2 are equal
  51.   //        false, otherwise
  52.  
  53.   node v;
  54.  
  55.   forall(v,*S1) 
  56.     if (! S2->member(v)) return false;
  57.  
  58.   forall(v,*S2) 
  59.     if (! S1->member(v)) return false;
  60.  
  61.   return true;
  62.  
  63.  }
  64.  
  65.  
  66.  
  67.  
  68. //------------------------------------------------------------------------------
  69. // Epsilon Closure
  70. //------------------------------------------------------------------------------
  71.  
  72. void E_CLOSURE(NFA& A, node_set_ptr T)
  73. {
  74.   /* expands node set *T by dfs on the epsilon edges */
  75.  
  76.   stack<node> S;
  77.  
  78.   node u,v;
  79.   edge e;
  80.  
  81.   forall(v,*T) S.push(v);
  82.  
  83.   while ( ! S.empty() )
  84.    { u = S.pop();
  85.  
  86.      // visit all neighbors v of u not in T and reachable by an epsilon-edge 
  87.  
  88.      forall_adj_edges(e,u)
  89.      { v = A.target(e);
  90.        if ( A.inf(e) == EPSILON && !T->member(v) ) 
  91.         { T->insert(v);
  92.           S.push(v);
  93.          }
  94.       }
  95.     }
  96.  
  97.  } // E_CLOSURE
  98.  
  99.  
  100. //------------------------------------------------------------------------------
  101. // Move
  102. //------------------------------------------------------------------------------
  103.  
  104. node_set_ptr MOVE(NFA& A, node_set_ptr T, char x)
  105. {
  106.   /* result is a pointer p to the set of nodes to which there 
  107.      is a transition on input symbol x from a node in *T
  108.   */
  109.  
  110.   node v;
  111.   edge e;
  112.  
  113.   node_set_ptr p = new set<node>;  
  114.   /* now p is a pointer to an empty set  of nodes */
  115.  
  116.   forall(v,*T)
  117.     forall_adj_edges(e,v)
  118.       if ( A.inf(e) == x ) p->insert(A.target(e));
  119.  
  120.   return p;
  121.  
  122. } // MOVE
  123.  
  124.  
  125.  
  126. //------------------------------------------------------------------------------
  127. // Build a DFA from an NFA
  128. //------------------------------------------------------------------------------
  129.  
  130. DFA  BUILD_DFA_FROM_NFA(NFA& A, node s0)
  131. {
  132.   // result is a DFA B accepting the same language
  133.   // as NFA A with initial state s0
  134.  
  135.  
  136.   DFA B;
  137.  
  138.   stack<node> S;
  139.  
  140.   node v,w;
  141.   char c;
  142.   node_set_ptr p;
  143.  
  144.   /* First we create a DFA-node for epsilon-closure(s0)and push it 
  145.      on the stack S. S contains all nodes of DFA B whose transitions 
  146.      have not been examined so far.  
  147.   */
  148.  
  149.   p = new set<node>;
  150.   p->insert(s0);
  151.   E_CLOSURE(A,p);
  152.   S.push(B.new_node(p));
  153.  
  154.   while ( ! S.empty() )
  155.   { v = S.pop();
  156.  
  157.     for(c = 'a'; c<='z'; c++)  // for each input symbol c do
  158.      {
  159.        p = MOVE(A,B.inf(v),c);
  160.  
  161.        // Is there any NFA-transisition from a node in B.inf(v) ?
  162.        // i.e.: Is p not empty ?
  163.  
  164.        if ( ! p->empty() )     
  165.         {
  166.           // compute the epsilon closure of *p
  167.  
  168.           E_CLOSURE(A,p);
  169.    
  170.  
  171.           /* search for a DFA-node w with B.inf(w) == *p */
  172.  
  173.           bool found = false;       
  174.           forall_nodes(w,B)
  175.             if (EQ_NODE_SET(B.inf(w),p))
  176.                { found = true;
  177.                  break;
  178.                 }
  179.  
  180.           /* if no such node exists create it */
  181.    
  182.           if ( !found )                     
  183.            { w = B.new_node(p);
  184.              S.push(w);
  185.             }
  186.    
  187.           /* insert edge [v] --(c)--> [w] */
  188.  
  189.           B.new_edge(v,w,c);               
  190.  
  191.          } // if p not empty
  192.    
  193.       }  // for c = 'a' ... 'z'
  194.  
  195.    } // while S not empty
  196.  
  197.  return B;
  198.   
  199. }
  200.  
  201.  
  202.   
  203.  
  204. main()
  205. { 
  206.  
  207.   // Build a NFA A
  208.  
  209.   NFA A;
  210.  
  211.   // States = {0,1,...,N-1}
  212.  
  213.   int N = read_int("number of states N = ");
  214.  
  215.   cout << "Start state = 0\n";
  216.  
  217.   array<node> state(0,N-1);
  218.  
  219.   int i,j;
  220.   char c;
  221.  
  222.   // create N nodes: state[0], ... , state[N-1]
  223.  
  224.   loop(i,0,N-1) state[i] = A.new_node(i);
  225.  
  226.  
  227.   // create edges (transistions)
  228.  
  229.   cout << "Enter Transitions of NFA (terminate input with   0 0 0)\n";
  230.   
  231.  
  232.   for(;;)
  233.   { cout << "state1  state2  label : ";
  234.     cin >> i >> j >> c;
  235.     if (i==0 && j==0 && c=='0') break;
  236.  
  237.     A.new_edge(state[i], state[j], c);
  238.    }
  239.  
  240.   node u,v;
  241.   edge e;
  242.  
  243.   // output  NFA A:
  244.  
  245.   newline;
  246.   cout << "NFA A: \n";
  247.  
  248.   forall_nodes(v,A)
  249.     { cout << string(" [%d] : ",A.inf(v));
  250.       forall_adj_edges(e,v) 
  251.         cout << string(" [%d]--%c-->[%d] ",A.inf(v),A.inf(e),A.inf(A.target(e)));
  252.       newline;
  253.      }
  254.  
  255.   DFA B = BUILD_DFA_FROM_NFA(A,state[0]);
  256.  
  257.  
  258.   // output  DFA B:
  259.  
  260.   node_array<int> name(B);
  261.  
  262.   newline;
  263.   cout << "DFA B:\n";
  264.   i=0;
  265.   forall_nodes(v,B)
  266.     { name[v] = i++;
  267.       cout << string(" [%d] = {",i);
  268.       forall(u,*B.inf(v)) cout << " " << A.inf(u);
  269.       cout << " }\n";
  270.      }
  271.   newline;
  272.  
  273.   forall_nodes(v,B)
  274.     { cout << string(" [%d] : ",name[v]);
  275.       forall_adj_edges(e,v) 
  276.         cout << string(" [%d]--%c-->[%d] ",name[v],B.inf(e),name[B.target(e)]);
  277.       newline;
  278.      }
  279.  
  280.   return 0;
  281. }
  282.